1. Field of the Invention
This invention relates to a coding system and the coding method in encoding information source symbols of an image. Specifically, this invention relates to a coding system and the coding method which finishes the decoding correctly when a transmitter site does not transmit the total number of information source symbols to a receiver site at the beginning of the code transmission.
2. Description of the Related Art
In a conventional coding system, there is a case which cannot know the total number of the original information source symbols from the code symbols at decoding time. For an example of image coding, as shown in ISO/IEC DIS 11544: "Progressive Bi-level Image Compression", a horizontal size H (the number of horizontal pels) and a vertical size V (the number of lines) of the image are previously transmitted from the transmitter site to the receiver site by using given fields in a header before the code transmission. Herein, pels stand for picture elements.
At the receiver site, the total number of the source symbols can be calculated as the product of the horizontal size by the vertical size. Therefore, the receiver site can judge an end of the source symbols correctly. Thus, at the receiver site, the decoding finishes according to the code received from the transmitter site without missing the end of the information source symbols. (The above-described system will be called as a conventional system, hereinafter).
In the above-described conventional system, a binary symbol stream is treated as the information source symbols and an enough memory which can store one page of the image as an object of coding is provided at the transmitter site. As pre-conditions to get the number of lines, a prescan of one page of the image must be performed. The number of lines can be transmitted through the header with the number of horizontal pels.
There is shown a block diagram of a configuration of an apparatus according to the above-described conventional system in FIG. 36. In the figure, an input data 1 is a pel of an input image. A symbol 2 is a binary symbol transferred from a probability estimator 11a (described later) to an entropy encoder 12 (described later) as an object of coding. A state 3 is a representative value of the estimated occurrence probability ratio of the symbol 2 output from the probability estimator 11a and input to the entropy encoder 12 (described later). A code data 4 is output from the entropy encoder 12 (described later) and input to an entropy decoder 13 (described later). A symbol 5 is a binary symbol transferred From an entropy decoder 13 (described later) as an object of decoding to a probability estimator 14a (described later). A state 6 is a representative value of the estimated occurrence probability ratio for the symbol 5 output from the probability estimator 14a (described later) and input to the entropy decoder 13 (described later). An output data 7 is a pel of an output image. The entropy encoder 11a outputs the symbol 2 which is an object of encoding after a predicted conversion. The entropy encoder 11a outputs the state 3 which is a representative value of the estimated occurrence probability ratio of the symbol 2. The entropy encoder 11a has a H counter 21a (described later) and a V counter 22a (described later) inside, The entropy encoder 12 inputs the symbol 2 and the state 3 and outputs the code data 4. The entropy decoder 13 inputs the code data 4 and the state 6 output from the probability estimator 14a for the symbol 5 and outputs the symbol 5 as an object of decoding. The probability estimator 14a outputs the state 6 which is a representative value of the estimated occurrence probability ratio for the symbol 5. The probability estimator 14a performs a predicted inversion of the symbol 5 input from the entropy decoder 13. And the probability estimator 14a outputs the output data 7 got after the predicted inversion. The probability estimator 14a has a H counter 23a (described later) and a V counter 24a (described later) inside. The H counter 21a counts the number of pels by every processing of input data up to the number of horizontal pels (H) transmitted through the header. The V counter 22a counts the number of lines by every processing of lines up to the number of lines (V) transmitted through the header. The H counter 23a counts the number of pels by every processing of output data up to the number of horizontal pels (H) received through the header. The V counter 24a counts the number of lines by every processing of lines up to the number of lines (V) received through the header.
A header 41a includes the number of horizontal pels (H) and the number of lines (V). A plurality of encoding control signals 50a are output for controlling the entropy encoder from the probability estimator 11a. A plurality of decoding control signals 70a are output for controlling the entropy decoder 13 from a probability estimator 14a.
FIG. 37 illustrates the number of horizontal pels (H) and the number of lines (V). In FIG. 37, there is shown a page input to a facsimile or a scanner. In this case, the page is scanned in the vertical direction and the horizontal direction by 300 dots per inch. When the size of the page is assumed to be 8.5 inch.times.11 inch, the number of horizontal pels (H) and the number of lines (V) can be got according to the following formula.
The number of horizontal pels (H)=8.5.times.300=2550 pels
The number of lines (V)=11.times.300=3300 lines
A sequence of the code data according to the conventional method is shown in FIG. 38.
The code data 4 contains a header 41 and a code 42 (described later). The number of the horizontal pels (H) 43a and the number of lines (V) are transmitted through the header 41.
Before the entropy encoder 12 transmits the code 42 to the entropy decoder 13, the header 41 of the code data 4 is transmitted and the number of horizontal pels 43a and the number of lines 44a are transmitted before beginning the decoding process of the entropy decoder 13,
The operation of a configuration of the figure will be explained, The probability estimator 11a performs the predicted conversion from the predicted value that is predicted for the input data 1. The probability estimator 11a outputs the symbol 2. The symbol 2 is an object of coding and indicates the conformity or nonconformity as a result of comparison between a predicted value and an actual value of the information source symbol 1. The probability estimator 11a outputs the state 3 predicted for the symbol 2 to the entropy encoder 12. The entropy encoder 12 inputs the symbol 2 and the state 3 from the probability estimator 11a as parameters of encoding. The entropy encoder 12 produces the code data 4 and outputs the code data 4 to an entropy decoder 13. The entropy decoder 13 inputs the code data 4 output from the entropy encoder 12 and the state 6 output from the probability estimator 14a for the symbol 5 which is an object of decoding. The entropy decoder 13 outputs the symbol 5 to the probability estimator 14a. The probability estimator 14a outputs the state 6 predicted for the symbol 5 to the entropy decoder 13. The probability estimator 14a performs a predicted inversion based on the symbol 5 input from the entropy decoder 13 and a predicted value that is predicted for the symbol 5. If the symbol 5 indicates conformity with the predicted value, the predicted value is output as the output data 7. If the symbol 5 indicates nonconformity with the predicted value, the non-predicted value (which is an inverted value of the predicted value) is output as the output data 7.
FIG. 39 shows a block diagram of a conventional encoder. To simplify the explanation, as shown In FIG. 40, reference symbols are assumed to be symbols A, B, C, D, E located on the same scanning line and the previous scanning line which are correlated with object symbol X.
In FIG. 39, a line buffer 201 stores at least two lines of the information source symbols (corresponding to the input data 1 in FIG. 36) from the image data. The line buffer 201 selects reference symbols A, B, C, D, E in FIG. 40 and outputs the reference symbols A, B, C, D, E as a reference symbol pattern 102. A memory controller 202 outputs a state 3 and a predicted value 105 from the reference symbol pattern 102. A table 203 for each pair of the state 3 and the predicted value indicated by the reference symbol pattern 102 is stored in the memory controller 202. A prediction convertor 205 produces a predicted conversion symbol 2 (corresponding to the symbol 2 in FIG. 36) from the information source symbol 1 based on the predicted value 105. A table 206 for a region width 108 outputs a region width 108 of an arithmetic code based on the state 3 output from the memory controller 202. An arithmetic encoder 207 performs arithmetic encoding.
A H count controller 300 sets the number of horizontal pels (H) at a H register 21r and controls the count in the H counter 21a. A V count controller 400 sets the number of lines (V) at a V register 22r and controls the count in a V counter 22a. A header generator 500 generates the header 41a with the number of horizontal pels (H) and the number of lines (V). An encoding controller 600 controls encoding process by issuing the encoding control signal 50a.
A selector 700 selects a header 41a output by the header generator 500 or a code 42 output by the arithmetic encoder 207 according to a select signal 51 in the encoding control signals 50a output from the encoding controller 600. The selector 700 outputs the code data 4 which is the selected code 42 or header 41a.
There is shown an example of a table 203 for the predicted value in FIG. 41. The table 203 for the predicted value stores a state 3 and a predicted value 105, corresponding to the reference symbol pattern 102. That is, the table 203 for a predicted value stores the state 3 and the predicted value 105 corresponding to the value of the reference symbols A, B, C, D, E.
As shown in FIG. 41, a state identifies a group of 16. In this case, the higher the predicted occurrence probability ratio of the predicted value is, the higher the value of the state is.
Next, the operation will be explained. The information symbol 1 (the image data 1) is stored in the line buffer 201 in units of lines. From the line buffer 201, symbols A, B, C, D, E in FIG. 39 are selected and output as the reference symbol pattern 102. The predicted value 105 and the state 3 for the coding symbol are output from the memory controller 202. And, the state 3 is converted to the region width 108 at the table 206 for the region width shown In FIG. 6. The region width 108 is output to the arithmetic encoder 207.
On the other, the prediction convertor 205 takes exclusive OR of the predicted value 105 and the information symbol 1 and produces the predicted conversion symbol 2. The predicted conversion symbol indicates zero (MPS: More Probable Symbol) when the predicted value conforms with the actual value of the information source symbol 1. And, the predicted conversion symbol indicates one (LPS: Less Probable Symbol) when the predicted value doesn't conform with the actual value of the information source symbol 1. Further, the reference symbol pattern is used as an index of the table 203. The predicted value and the state are cited from the table 203. The predicted conversion symbol 2 is input to the memory controller 202 to update the predicted value and the state dynamically. The memory controller 202 judges the timing point of the update and updates the predicted value and the state,
The arithmetic encoder 207 performs encoding process based on the region width 108 by mapping the predicted conversion symbol 2 on number line. Hereafter, the next information symbol is encoded as described above.
The H count controller 300 has the H register 21r which registers the number of horizontal pels (H). The V count controller 400 has the V register 22r which registers the number of lines (V). The number of horizontal pels (H) and the number of lines (V) are previously stored through the prescan at the H register 21r and the V register 22r, respectively.
The header generator 500 refers the number of horizontal pels and the number of lines set at the registers and generates the header 41a. The generated header 41a is selected at the selector 700 and output as the code data 4. After that, encoding process of the image data is performed by the arithmetic encoder 207 and the code 42 output from the arithmetic encoder 207 is selected by the selector 700. Then, the code 42 is output as the code data 4.
The encoding controller 600 outputs a signal 52 by every processing of a pel to the H count controller 300. And a signal 53 is output by every processing of one symbol to the arithmetic encoder 207. Because processing of one symbol is performed, corresponding to one pel, the signal 52 is identical with the signal 53. That is, in this example, the number of information source symbols 1 is equal to the number of predicted conversion symbols 2. The H count controller 300 counts either the number of information source symbols 1 or the number of predicted conversion symbols 2.
The H count controller 300 increments the value in the H counter by every receiving of the signal 52. When the value in the H counter reaches the number of horizontal pels set at the H register, the H count controller 300 issues a carry signal 109.
The V count controller 400 increments the value in the V counter by every receiving of the carry signal 109. When the value in the V counter reaches the number of lines set at the V register, the V count controller 400 issues a carry signal 110. When the carry signal 110 is issued, the encoding controller judges the end of the encoding process. Thus, the encoding process is completed.
The carry signal 109 is input to the line buffer 201. The line buffer 201 judges the end of the processing of one line by every input of the carry signal 109. The line buffer 201 deletes the processed line which is not needed for referring pels and starts to store new lines. Thus, the line buffer 201 is updated.
Herein, the arithmetic encoding will be described in detail.
In case that the i-th symbol in the predicted conversion symbol stream is assumed to be a.sub.1 and the mapping region (assigned region) of the LPS at the i-th point is assumed to be Qe, if the region for the MPS is set under the effective region, the mapping region (effective region) A.sub.i of the symbol stream at the i-th point and the lower bound coordinates value C.sub.i are,
when the symbol a.sub.i indicates the MPS and initial-values are set as A.sub.0 =1, C.sub.O =0,
A.sub.i =A.sub.i-1 -Qe PA1 C.sub.i =C.sub.i-1 PA1 A.sub.i =Qe PA1 C.sub.i =C.sub.i-1 +(A.sub.i-1 -Qe) PA1 renormalized value of A.sub.i =A.sub.i * 2.sup..rect-ver-solid. PA1 (1/2&lt;=renormalized value of A.sub.i *1) PA1 renormalized value of C.sub.i =C.sub.i *2.sup..rect-ver-solid. PA1 A.sub.i =A.sub.i-1 -Qe PA1 C.sub.i =C.sub.i-1 PA1 A.sub.i =Qe PA1 C.sub.i =C.sub.i-1 -(A.sub.i-1 -Qe) PA1 decoder Information source unit memory means for storing the information source unit; PA1 decoder information source unit count means for counting the number of information source units stored in the decoder information source unit memory means; and PA1 decode terminate means receiving the number of information source units from the notify means, for comparing the number of information source units counted by the decoder information source unit count means and the number of information source units notified by the notify means, and for terminating the decoding according to a result of the comparison. PA1 means for inputting a plurality of information source symbols to be encoded, PA1 means for selecting a finite number of encoded information source symbols as reference symbols, PA1 means for predicting an encoded information source symbol based on the reference symbols, PA1 means for estimating an occurrence probability of the predicted symbol, PA1 means for representing the estimated occurrence probability by one of a finite number of representing values, PA1 means for performing a conversion from the information source symbol to a predicted conversion symbol according to the information source symbol and the predicted information source symbol, and PA1 means for outputting the predicted conversion symbol and the representing value; PA1 means for receiving the predicted conversion symbol and the representing value from the probability estimator means, PA1 means for performing an entropy encoding of the predicted conversion symbol according to the representing value and outputting an encoded symbol, and PA1 means for placing a terminate code, which is distinguishable from the encoded symbol stream, at the end of the encoded symbol stream at the end of encoding; and PA1 means for defining a size of an information source unit, PA1 means for counting a total number of information source units during encoding, PA1 means for placing the total number of information source units in the terminate code at the end of the entropy encoding; and, PA1 decoder probability estimator means including PA1 decoder information source unit memory means for storing an information source unit which corresponds to the information source unit of the encoder; PA1 decode terminate means for recognizing the End Of Sequence symbols inserted between the information source units and for deciding the termination of the information source symbols decoding based on the End Of Sequence symbols. PA1 means for inputting a plurality of information source symbols to be encoded, PA1 means for selecting a finite number of information source symbols as reference symbols, PA1 means for predicting an incoming information source symbol based on the reference symbols, PA1 means for estimating an occurrence probability of the predicted symbol, PA1 means for representing the estimated occurrence probability by one of a finite number of representing values, PA1 means for performing a conversion from the information source symbol to predicted conversion symbol according to the information source symbol and the predicted symbol, PA1 means for outputting the predicted conversion symbol and the representing value of the estimated occurrence probability for the predicted information source symbol to entropy encoding means; PA1 entropy encoding means including PA1 detect means for detecting an occurrence of predefined encoding pattern during a information source symbol encoding; PA1 dummy symbol adding means for adding a dummy symbol to the predefined encoding pattern detected by the detect means in the encoder; PA1 terminate symbol sequence adding means for adding a terminate symbol sequence which has the predefined encoding pattern and terminate symbol indicating a termination of information source symbols at the end of the information source symbol encoding; and PA1 wherein the decoder may include: PA1 probability estimator means including
when the symbol a.sub.i indicates the LPS,
Here, in case that the value in the effective region A.sub.i indicates less than 1/2, the value is multiplied by exponentiation of 2 to improve the arithmetic calculation accuracy. In this case, an overflow of the coordinates value C.sub.i (a portion above the radix point) is output as a bit stream of code data. Hereafter, the process of the exponentiation is called as a renormalization.
In arithmetic codes, it is known that the highly effective encoding process can be performed when the value Qe is set to be the occurrence probability ratio of the LPS (the predicted error probability ratio). The length of the code can be nearly equal to the value of the information source entropy. As a result, an arithmetic encoding process can be performed according to the above-described processing by selecting the value Qe suitable for the predicted error probability ratio or the approximate value corresponding to the state.
FIG. 42 illustrates an example of a table of a state S and a region width Qe. On the table, the value in the above-described formula is multiplied by 2.sup.16. In this case, the region calculation on number line is performed with 16 bit precision. And, each of the value A.sub.i and C.sub.i attains 16 bit precision below the radix point.
FIG. 43 is a block diagram of a decoder. An arithmetic decoder 214 reproduces the predicted conversion symbol 5 (the decoded symbol) based on a region width 108 from the code data 4. A prediction invertor 216 reproduces the information source symbol 1 according to an exclusive OR operation. A decoding controller 610 controls decoding issuing a decoding control signals 70a. A selector 710 selects a header 41a and a code 42. A header decoder 510 extracts the number of horizontal pels and the number of lines from the header 41a. Other elements are the same as in the encoding apparatus shown in FIG. 39.
An arithmetic decoder 214 performs an arithmetic decoding by every one symbol.
In case of decoding arithmetic codes, it is assumed that the relative coordinates value is assumed to be and C.sub.i, the region width of the LPS for the i-th predicted conversion symbol a.sub.i is assumed to be Qe and initial-values are set as A.sub.0 =1, C.sub.0 =code output from the encoder.
When C.sub.1 &lt;(A.sub.i-1 -Qe), a.sub.i indicates the MPS,
when C.sub.i-1 &gt;=(A.sub.i-1 -Qe), a.sub.i indicates the LPS,
Here, when the value in the effective region A.sub.i is less than 1/2, the value is multiplied by exponentiation of 2 as the renormalization process. In this case, code data of m bit is input as the least or less significant of the value C.sub.i.
renormalized value of A.sub.i =A.sub.i * 2.sup..rect-ver-solid.
(1/2&lt;=renormalized value of A.sub.1 &lt;1)
renormalized value of C.sub.i =C.sub.i * 2.sup..rect-ver-solid.
A prediction invertor 216 reproduces the information source symbol 1 bit by bit. The prediction invertor 216 outputs a predicted value 105 when the predicted conversion symbol is the MPS. The prediction invertor 216 outputs the inversion when the predicted conversion symbol is the LPS.
There is shown a processing flow chart in FIG. 44. As shown in FIG. 44, the number of horizontal pels (H) and the number of lines (V) are set through the prescan at the H register 21r and the V register 22r, respectively. The probability estimator 11a produces the header that includes number of horizontal pels (H) set at the H register 21r and number of lines (V) set at the V register 22r and transmits the header to the receiver site. And, the probability estimator 11a clears the value in the H counter 21a and in the V counter 22a. Then, when the encoding process of the input data 1 is performed, the value of the H counter 21a is incremented by one, and when the value in the H counter 21a reaches the number of horizontal pels (H) transmitted through the header, the value in the V counter 22a is incremented by one and the value in the H counter 21a is cleared. Then, when the value in the V counter 22a reaches the number of lines (V) transmitted through the header, the input data 1 comes to an end. Thus, encoding process is completed.
There is shown a processing flow chart of the decoding process in FIG. 45. A probability estimator 14a, as shown in FIG. 45, detects the number of horizontal pels and the number of lines (V) from the header at the beginning of decoding process and stores each of them at the H register 23r and the V register 24r, respectively. The probability estimator 14a clears the value in the H counter 23a and in the V counter 24a. When the decoding process of the output data 7 is performed, the value in the H counter 23a is incremented.
When the value in the H counter 23a reaches the number of horizontal pels (H) transmitted through the header, the value in the V counter 24a is incremented and the value in the H counter 23a is cleared. Then, the decoding process comes to an end when the value in the V counter 24a reaches the number of lines (V) received through the header.
Problems to be Solved by the Invention
So that the end of information source symbols is judged at the receiver site for decoding information source symbol, the decoding termination method which notifies the total number of information source symbols as a parameter information Is adapted. For example, when the image is treated as information source symbols, as shown in the conventional example, the total number of information source symbols is previously transmitted by indicating the horizontal size (the number of horizontal pels) and the vertical size (the number of lines) in the header. At the transmitter site, the only method to detect the total number of lines is by storing one page of the image in the memory at once. In an apparatus which does not have an enough memory to store one page of the image, the detection of the number of lines can't be performed by using the conventional header notification.